In data warehouse environment, data are organized based on star schema \cite{stonebraker:dw} and
the analytical query is star join query which has several foreign-key joins between fact table and
dimension tables followed by aggregation and sort. 
To understand the impact of various characteristics on query performance on GPU,
we start measurement from single query operator. We choose selection, join(hash join),
aggregation and sort as the representative operators and comprehensively study each operator's performance under
various conditions.
Then we measure the performance of analytical query on GPU using the Star Schema Benchmark queries
which can good represent the query characteristics in data warehouse environment.

\subsection{Single Query Operator}

\subsubsection{Selection}
Selection can be represented in the following format:\\
\\\textbf{Select} L1, L2,...\\
\textbf{From} R\\ 
\textbf{Where} predicate;
\\

The semantics of the selection operator is simple. It sequentially scans a table 
and projects the tuples that meet the predicate condition.

The key factors that affect the selection performance include 
selectivity,
the tuple number of the table,
the number of projected columns,
the width of the projected column,
the number of prediate
and the complexity of the predicate.\\

\textbf{Selectivity}

We vary the selectiviy of from 1\% to 100\% and keep other factors simple as possible.\\

\textbf{Tuple number}

we vary the tuple number from. \\

\textbf{Number of projected number}

we vary the number of projected number from 1 to 10.\\

\textbf{Projected tuple size}

We vary the projected tuple size from 1 to 50.\\

\textbf{Number of predicates}

We vary the number of predicates from 1 to 5.\\

\textbf{Predicate complexity}
to be finished. \\

\subsubsection{Join}
Join can be represented in the following format:\\
\\\textbf{Select} R1,R2..., S1,S2...\\
\textbf{From} R, S\\
\textbf{Where} R.key = S.key;
\\

Our measurement focuses on two representative hash join algorithms: the unpartitioned hash join
and the radix hash join.

\textbf{Unpartitioned hash join}

The unpartitioned hash join first builds a hash table for the entire dimension table. Then it sequentially
scans the fact table and probes the hash table to find a match. Tuple will be projected by the operator
only if a corresponding match is found during the probe.

\textbf{Radix hash join}

The radix hash join first partitions both dimension table and fact table into the same number of partitions.
Then each pair of the partitions are joined to generate the projected columns. To get a better
performance, the average partition size of the dimension table should not exceed the size of the cache. 

The key factors that impact the join performance include join selectivity, the number of projected columns from fact table
and dimension table, the tuple number of dimension table and fact table and the attribute size of the projected columns.

\subsubsection{Aggregation}
Aggregation can be represented in the following format:\\
\\\textbf{Select} L1, L2,...\\
\textbf{From} R\\ 
\textbf{Group By} Key;
\\

There exist two major aggregation methods in the current system: hash based aggregation and sort based aggregation.
We focus on hash based aggregation here.

The hash based aggregation first caculates a hash value for each group by key.
The tuples that have the same hash value are placed into the same group. Then the aggregation
function can be calculated for each group.

The key factors that affect the performance of aggregation include the width of the group by key, the complexity
of the aggregation function and the number of projected columns. 

\subsubsection{Sort}
Sort can be represented in the following format:\\
\\\textbf{Select} L1, L2,...\\
\textbf{From} R\\ 
\textbf{Order By} Key;
\\

The representing sort algorithms are radix sort and merge sort.

\textbf{Radix sort}

\textbf{Merge sort}

The factors that affect the performance of sort include the width of the key and the tuple size of the projected
columns. 

\subsection{Analytical Query}
We use the Star Schema Benchmark queries as the workloads to measure the performance of analytical query on GPU. 
